package com.xie.leetcode.array;

//169. 多数元素
//        给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
//
//        你可以假设数组是非空的，并且给定的数组总是存在多数元素。
//
//
//
//        示例 1：
//
//        输入：[3,2,3]
//        输出：3
//        示例 2：
//
//        输入：[2,2,1,1,1,2,2]
//        输出：2

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author xiezhendong
 * @date 2021/10/26
 */
public class MajorityElement {

    public static void main(String[] args) {
        MajorityElement majorityElement = new MajorityElement();
        System.out.println(majorityElement.majorityElement(new int[]{3, 2, 3}));
        System.out.println(majorityElement.majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2}));
    }


    public int majorityElement(int[] nums) {
        List<Integer> numsList = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int number = nums.length / 2;
        HashMap<Integer, Integer> numsMap = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (numsList.contains(num)) {
                continue;
            }
            numsMap.merge(num, 1, Integer::sum);
            if (numsMap.get(num) > number) {
                numsList.add(num);
            }
        }
        return numsList.get(0);
    }
}
